package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1743 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[] restoreArray(int[][] adjacentPairs) {
            Map<Integer, Set<Integer>> nextMap = new HashMap<>();
            for (int[] adjacentPair : adjacentPairs) {
                putCnt(nextMap, adjacentPair[0], adjacentPair[1]);
                putCnt(nextMap, adjacentPair[1], adjacentPair[0]);
            }

            int curStart = 0, prev = 100002;
            for (Integer key : nextMap.keySet()) {
                if (nextMap.get(key).size() == 1) {
                    curStart = key;
                    break;
                }
            }

            int[] res = new int[adjacentPairs.length + 1];
            for (int i = 0; i < res.length; i++) {
                res[i] = curStart;
                for (Integer next : nextMap.get(curStart)) {
                    if (next != prev) {
                        prev = curStart;
                        curStart = next;
                        break;
                    }
                }
            }

            return res;
        }

        public void putCnt(Map<Integer, Set<Integer>> nextMap, int key, int val) {
            if (!nextMap.containsKey(key)) nextMap.put(key, new HashSet<>());
            nextMap.get(key).add(val);
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] arr = InputUtil.toDoubleIntegerArray("[[100000,-100000]]");
        System.out.println(Arrays.toString(solution.restoreArray(arr)));
    }

    public static void main(String[] args) throws Exception {
        LC1743 an = new LC1743();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
